#include <vector>
#include <iostream>
#include <algorithm>
#include <queue>
#include <stdio.h>
using namespace std;

struct Node
{
	int x;
	int y;

	bool operator < (const struct Node& node) const 
	{
		if (y != node.y)
			return y < node.y;
		else
			return x > node.x;
	}

	struct Node& operator = (const struct Node& node)
	{
		this->x = node.x;
		this->y = node.y;
		return *this;
	}
};

class Solution
{
public:
	int maxArea(vector<int>& height)
	{
		if (height.size() <= 1)
			return 0;

		int ans = 0;
		priority_queue<Node> q;

		for (size_t i=0, si=height.size(); i<si; ++i)
		{
			Node node;
			node.x = i;
			node.y = height[i];
			q.push(node);
		}
	
		while (q.size() > 1)
		{
			Node left = q.top();
			q.pop();
			
			Node right = left;
			Node tmp;

			while (!q.empty())
			{
				tmp = q.top();
				if (tmp.y == right.y)
				{
					right = tmp;
					q.pop();
				}
				else
					break;
			}

			if (right.x == left.x)
			{	
				left.y = tmp.y;
				q.push(left);
			}
			else
			{
				ans = max(ans, (right.x - left.x) * left.y);
				left.y = right.y = tmp.y;
				q.push(left);
				q.push(right);
			}
			if (q.size() == 2)
			{
				left = q.top(); q.pop();
				right = q.top(); q.pop();
				ans = max(ans, (right.x - left.x) * left.y);
				break;
			}
			if (q.size() < 2)
				break;
		}
		return ans;
	}
};
